(1) Field of the Invention
The invention relates to an arrangement for real-time calculation of the discrete cosine transformation coefficients of a group of N inputs samples of a digital input signal. It is particularly intended for performing a transform coding of a digitalized video signal to reduce its bit rate. Such an arrangement will hereinafter be referred to as a DCT arrangement.
The invention also relates to an arrangement for calculating the original N input samples from the coefficients thus obtained. Such an arrangement will be referred to as an IDCT arrangement.
(2) Description of the Prior Art
As is generally known, transform coding is a data reduction method in which a television picture is divided into blocks of N.times.N picture elements and in which each block is considered to be a sum of a series of (N.times.N) mutually orthogonal basic pictures B(i,k) where i,k=0, . . . , N-1, each with its own weighting factor y(i,k). Data reduction is possible because the information is concentrated only in a limited number of non-correlated basic pictures due to the correlation of the picture elements in a block, so that only the associated weight factors are important and the others can be ignored.
To indicate mathematically how the weighting factors are calculated, the block of N.times.N picture elements will be represented by an N.times.N matrix X, the weighting factors will be arranged in an N.times.N matrix Y and an N.times.N transform matrix A will be defined which is related to the set of basic pictures B(i, k). More particularly, there applies that: EQU B(i,k)=A.sub.i A.sub.k.sup.T. (1)
In this expression, A.sub.i represents a matrix in which each column is equal to the i-th column of the transform matrix A and A.sub.k.sup.T represents a matrix each row of which is equal to the k-th row of the matrix A. The weighting factors now follow from the matrix multiplication EQU Y=A.sup.T XA. (2)
In this expression, A.sup.T represents the transposed matrix of A. For more information relating to the above, reference is made to reference 1.
For the calculation of the weighting factors in accordance with expression (2), both the original transform matrix A and its transposed version A.sup.T must be available. However, expression (2) is equivalent to EQU Y.sup.T =(XA).sup.T A (3)
Only the transform matrix A needs to be available for this matrix multiplication. More particularly, the product matrix P=XA can be calculated first. Subsequently, P can be transposed and finally Y.sup.T =P.sup.T A can be calculated. An arrangement for performing the matrix multiplication indicated in expression (3) is described, for example in reference 2. For transposing P, use is made of an intermediate memory in which P is written in row by row and is read out column by column. Because both X and P.sup.T are multiplied by the same matrix A, one and the same circuit can be used for both multiplications.
In order to recover the original block of picture elements X from the weighting factors thus obtained, these weighting factors are subjected to an inverse transformation which is defined as follows: EQU X=AYA.sup.T ( 4)
In conformity with the foregoing this expression is equivalent to: EQU X=A(AY.sup.T).sup.T ( 5)
It is to be noted that a product matrix such as P=XA and Y.sup.T =PA in expression (3) or P'=AY.sup.T and X=AP'.sup.T in expression (5) is obtained from a series of vector matrix multiplications. In fact, each row of, for example, X is multiplied by A in order to find the corresponding row of P.
The number of non-negligible weighting factors appearing from such a transformation is found to be closely related to the structure of the basic pictures chosen and hence to the transform matrix chosen. The most optimum transform matrix which is nowadays frequently used is the discrete cosine transform matrix whose elements a(i,k) are defined as follows: ##EQU1##
Q is a scaling constant which is equal to 2/N if this matrix is used to calculate the weighting factors for the direct transformation and which is equal to 1 if it is used for the inverse transformation.
When two N.times.N matrices are multiplied by each other in a conventional way, which in that case is referred to as the direct method, N.sup.2 multiplications must be performed for each N product element of the product matrix and N(N-1) additions are required. A DCT arrangement whose implementation is based on this direct method is described, for example, in Reference 3. So-called fast methods are known from References 4 and 5 in which the desired result can be obtained with considerably fewer multiplications and additions. For example, only 13 multiplications are performed and only 29 additions are required when the method described in Reference 5 is used if N=8. The drawback of these known methods is that the intermediate results occurring during the calculation process must be very accurate due to subsequent further processing steps to be performed (this means that the word length of these intermediate results must be large). These further processing steps are notably multiplications.